Field
Various features generally relate to cryptographic security, and more particularly to methods and devices for fixed execution flow multiplier recoding and scalar multiplication used in cryptographic security algorithms.
Background
Elliptic curve point multiplication, and in general multiplication by a constant in a cyclic group with g elements, is a calculation that accepts a multiplier k (with k≧0) and a base P, and computes the result:
      k    ·    P    =                    P        +        P        +        …        +        P                    ︸                  k          ⁢                                          ⁢          summands                      .  This operation is called scalar multiplication, and it is a fundamental operation in many cryptographic protocols, for instance Diffe-Hellman key-exchange and generating digital signatures.
Generally, k·P may be calculated by first writing out the multiplier k as k=Σi=0lki2i where ki are elements of a integer digit set D. First, let there be a Z that is initialized to the additive identity, which for elliptic curves is called the point at infinity. Next, the digits ki of k are examined from most significant to least significant. For a digit ki, if 0 then Z:=2*Z. If ki≠0, then Z:=2*Z+ki*P. When all the bits have been processed the result is the then current value of Z. However, methods utilizing such expansions are susceptible to side-channel analysis attacks and timing analysis attacks because the sequence of zero and non-zero digits is not regular thereby leaking some information about the multiplier k.
A prior art method developed by Nicholas Theriault reduces the risk of side-channel analysis and timing analysis. Nicholas Theriault, SPA Resistant Left-to-Right Integer Recodings, Selected Areas in Cryptography (2005): pages 345-358. Theriault expands the multiplier k as the expansion k=Σi=0lki2wi where w is a window length parameter and ki is chosen from one of two sets of integers:                Digit Set #1: {±1}∪{±2, ±4, . . . , ±2w} for a window w;        Digit Set #2: {±1, ±3, ±5, . . . , ±2w−1} for a window w.        
Theriault's method has some notable disadvantages though. First, Digit Set #2 can only expand odd digits. Consequently, Theriault suggests to use this multiplier expansion with groups of odd order and if the original multiplier k is even, to add an odd multiple of the group order g so that a new multiplier k′=k+n*g is odd. This has the drawback that it makes the multiplier longer, and therefore the scalar multiplication slower. Second, since k′>g, one of the intermediate computations may turn out to be equal to g·P. This leads to an exceptional case in the formula to compute with elliptic curves, the result being that this occurrence leaks information and may be detected by means of side-channel attacks.
Third, computing the multiplier expansion using Digit Set #2 will yield a carry of 0 or 1, which requires an extra operation or a dummy operation to fix the result. However, an extra operation would be detectable by means of side-channel attacks, and a dummy operation would be detectable by means of fault attacks. Thus, in both cases information is leaked and the parity of the multiplier may be revealed.
Accordingly, there is a need for methods and devices that can execute scalar multiplication in a time and memory efficient manner that are also resistant to side-channel attacks and fault attacks.